package sliding_window

/*
DNA序列由一系列核苷酸组成，缩写为'A','C','G'和'T'.。

例如，"ACGAATTCCG"是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中【出现不止一次的】长度为10的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

*/

//哈希表：用一个哈希表统计 s 所有长度为 10 的子串的出现次数
//时间复杂度：O(NL)，其中 N 是字符串 s 的长度，L=10 即目标子串的长度。
//空间复杂度：O(NL)
func findRepeatedDnaSequences(s string) (ans []string) {
	cnt := make(map[string]int)
	for i := 0; i <= len(s)-10; i++ {
		sub := s[i : i+10]
		cnt[sub]++
		if cnt[sub] == 2 {
			ans = append(ans, sub)
		}
	}
	return
}

//滑动窗口模板方法
func findRepeatedDnaSequencesTpl(s string) (ans []string) {
	//双指针和哈希表
	left, right, valid := 0, 0, make(map[string]int)

	//扩大窗口
	for right < len(s) {
		right++

		//收缩窗口
		for right-left >= 10 {
			if right-left == 10 {
				//截取序列
				valid[s[left:right]]++
				if valid[s[left:right]] == 2 {
					ans = append(ans, s[left:right])
				}
			}
			left++
		}
	}
	return
}

//由于 s 中只含有 4 种字符，我们可以将每个字符用 2 个比特表示，即：
//
// A 表示为二进制 00；
// C 表示为二进制 01；
// G 表示为二进制 10；
// T 表示为二进制 11。
//如此一来，一个长为 10 的字符串就可以用 20 个比特表示，而一个 int 整数有 32 个比特，足够容纳该字符串，因此我们可以将 s 的每个长为 10 的子串用一个 int 整数表示（只用低 20 位）。
//注意到上述字符串到整数的映射是一一映射，每个整数都对应着一个唯一的字符串，因此我们可以将方法一中的哈希表改为【存储每个长为 10 的子串的整数】表示。

//如果我们对每个长为 10 的子串都单独计算其整数表示，那么时间复杂度仍然和方法一一样为 O(NL)。为了优化时间复杂度，我们可以用一个大小固定为 10 的滑动窗口来计算子串的整数表示。
//设当前滑动窗口对应的整数表示为 x，当我们要计算下一个子串时，就将滑动窗口向右移动一位，此时会有一个新的字符进入窗口，以及窗口最左边的字符离开窗口，这些操作对应的位运算，按计算顺序表示如下：
//1.滑动窗口向右移动一位：x = x << 2，由于每个字符用 2 个比特表示，所以要左移 2 位；
//2.一个新的字符 ch 进入窗口：x = x | bin[ch]，这里 bin[ch] 为字符 ch 的对应二进制；
//3.窗口最左边的字符离开窗口：x = x & ((1 << 20) - 1)，由于我们只考虑 x 的低 20 位比特，需要将其余位置零，即与上 (1 << 20) - 1。
//将这三步合并，就可以用 O(1)的时间计算出下一个子串的整数表示，即 x = ((x << 2) | bin[ch]) & ((1 << 20) - 1)。

//时间复杂度：O(N)，其中 NN 是字符串 s 的长度。
//空间复杂度：O(N)。

//哈希表 + 滑动窗口 + 位运算
func findRepeatedDnaSequencesBit(s string) (ans []string) {
	const L = 10
	var bin = map[byte]int{'A': 0, 'C': 1, 'G': 2, 'T': 3}
	n := len(s)
	if n < L {
		return
	}

	x := 0
	//前十个字符的字符串的整数表示
	for _, ch := range s[:L-1] {
		x = x<<2 | bin[byte(ch)] //每个字符用2个比特表示，所以要左移2位 与上ch对应的二进制
	}
	cnt := map[int]int{}
	for i := 0; i <= n-L; i++ {
		x = (x<<2 | bin[s[i+L-1]]) & (1<<(L*2) - 1)
		cnt[x]++
		if cnt[x] == 2 {
			ans = append(ans, s[i:i+L])
		}
	}

	return ans
}
